package data_structure.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        if (numRows == 0) {
            return ans;   // 里面一行都没有
        }

        ans.add(new ArrayList<>());
        ans.get(0).add(1);
        if (numRows == 1) {
            return ans; // { { 1 } }
        }

        ans.add(new ArrayList<>());
        ans.get(1).add(1);
        ans.get(1).add(1);
        if (numRows == 2) {
            return ans; // { { 1 }, { 1, 1 } }
        }

        for (int i = 3; i <= numRows; i++) {
            // 结果中需要多添加一行
            List<Integer> curLine = new ArrayList<>();
            ans.add(curLine);
            // 新添加的这行的第一个元素一定是 1
            ans.get(i - 1).add(1);  // 等价于 curLine.add(1)
            // 处理除了最后一个元素以外的其他元素
            // 这个是第 i 行，一共有 i 个元素，除去第一个和最后一个，还剩 i - 2 个元素
            for (int j = 0; j < i - 2; j++) {
                // j = 0 的时候，需要计算该行的第 2 个元素
                // 由上一行的第 1 个元素和第 2 个元素相加
                // j = 1 的死后，需要计算该行的第 3 个元素
                // 由上一行的第 2 个元素和第 3 个元素相加
                // 计算该行的 j + 2 个元素
                // 由上一行的 j + 1 个元素和 j + 2 个元素
                // 换成下标之后，统一减一
                // 上一行的 [j] 和 [j + 1] 的元素
                // 当前行的下标 [i - 1]，上一行的下标就是 [i - 2]
                // 先得到上一行
                List<Integer> prevLine = ans.get(i - 2);
                int first = prevLine.get(j);
                int second = prevLine.get(j + 1);
                int e = first + second;
                curLine.add(e);
            }
            // 该行的最后一个元素还是 1
            curLine.add(1);
        }

        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.generate(0));
        System.out.println(solution.generate(1));
        System.out.println(solution.generate(2));
        System.out.println(solution.generate(3));
        System.out.println(solution.generate(4));
    }
}
